import org.junit.jupiter.api.DisplayName;
import org.junit.jupiter.params.ParameterizedTest;
import org.junit.jupiter.params.provider.Arguments;
import org.junit.jupiter.params.provider.MethodSource;

import java.util.*;
import java.util.stream.Stream;

/**
 * 字母异位词分组
 * 题目：给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。
 * <p>
 * 示例:
 * 输入: ["eat", "tea", "tan", "ate", "nat", "bat"]
 * 输出:
 * [
 * ["ate","eat","tea"],
 * ["nat","tan"],
 * ["bat"]
 * ]
 * 说明：
 * 所有输入均为小写字母。
 * 不考虑答案输出的顺序。
 * <p>
 * 来源：力扣（LeetCode-49）
 * 链接：https://leetcode-cn.com/problems/group-anagrams
 *
 * @author godfrey
 * @since 2020-10-28
 */
@DisplayName("字母异位词分组")
public class GroupAnagrams extends BaseTest {

    static Stream<Arguments> testArguments() {
        return Stream.of(
                Arguments.arguments((Object) new String[]{"eat", "tea", "tan", "ate", "nat", "bat"}),
                Arguments.arguments((Object) new String[]{"bdddddddddd", "bbbbbbbbbbc"})
        );
    }

    @DisplayName("按照字典序排序分类-时间复杂度O(nklognk)，空间复杂度O(nk)")
    @ParameterizedTest
    @MethodSource("testArguments")
    void groupAnagrams(String[] strs) {
        if (strs.length == 0) {
            System.out.println(-1);
        }
        Map<String, List<String>> ans = new HashMap<>();
        //按照字典序排序
        for (final String s : strs) {
            char[] tmp = s.toCharArray();
            Arrays.sort(tmp);
            final String key = new String(tmp);
            if (!ans.containsKey(key)) {
                ans.put(key, new ArrayList<>());
            }
            ans.get(key).add(s);
        }
        System.out.println(ans.values());
    }

    @DisplayName("按计数分类-时间复杂度O(nk)，空间复杂度O(nk)")
    @ParameterizedTest
    @MethodSource("testArguments")
    void groupAnagrams2(String[] strs) {
        if (strs.length == 0) {
            System.out.println(-1);
        }
        Map<String, List<String>> ans = new HashMap<>();
        int[] count = new int[26];
        for (String s : strs) {
            Arrays.fill(count, 0);
            for (char c : s.toCharArray()) {
                count[c - 'a']++;
            }
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < 26; i++) {
                sb.append('#');
                sb.append(count[i]);
            }
            String key = sb.toString();
            if (!ans.containsKey(key)) {
                ans.put(key, new ArrayList());
            }
            ans.get(key).add(s);
        }
        System.out.println(ans.values());
    }

    @DisplayName("算术基本定理(有溢出的可能）-时间复杂度O(nk)，空间复杂度O(nk)")
    @ParameterizedTest
    @MethodSource("testArguments")
    void groupAnagrams3(String[] strs) {
        HashMap<Long, List<String>> hash = new HashMap<>();
        //每个字母对应一个质数
        int[] prime = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103};
        for (String str : strs) {
            long key = 1;
            //累乘得到 key
            for (int j = 0; j < str.length(); j++) {
                key *= prime[str.charAt(j) - 'a'];
            }
            if (hash.containsKey(key)) {
                hash.get(key).add(str);
            } else {
                List<String> temp = new ArrayList<>();
                temp.add(str);
                hash.put(key, temp);
            }
        }
        System.out.println(hash.values());
    }
}
